package offer;

import java.util.Stack;

/**
 * @author cyt
 * @create 2020-05-31 22:14
 */
public class T40 {

    public static void main(String[] args) {

    }

    /**
     * 假设压入栈的所有数字均不相等。
     * 例如序列1,2,3,4,5是某栈的压入顺序，
     * 序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
     * 但4,3,5,1,2就不可能是该压栈序列的弹出序列。
     * （注意：这两个序列的长度是相等的）
     * @param pushA
     * @param popA
     * @return
     */
    public boolean IsPopOrder(int[] pushA, int[] popA) {

        if(pushA.length == 1 && popA.length == 1){
            return popA[0] == pushA[0];
        }
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int j = 0;
        stack.push(pushA[i++]);
        while (j < popA.length - 1) {
            // 栈顶元素等于出栈序列当前的元素
            if (stack.peek() == popA[j]) {
                j++;
                stack.pop();
            }
            // 不等于
            // 入栈
            if(i == pushA.length) return false;
            stack.push(pushA[i++]);

        }

        return true;
    }
}
